#include <stdio.h>
#include <stdlib.h>

int min(int a, int b, int c);
int distanceEdition(char* chaine1, char* chaine2, int tailleChaine1, int tailleChaine2){
  
  int d[2][tailleChaine2+1];
  int j;
  for (j=0; j <= tailleChaine2; j++)
    d[1][j] = j;
  int i;
  for (i=1; i <= tailleChaine1; i++) {
    d[0][0] = d[1][0];
    d[1][0]++;
    int a;
    for (a=1; a <= tailleChaine2; a++) {
      d[0][a]= d[1][a];
      d[1][a] = min(
		    d[0][a] + 1,
		    d[1][a - 1] + 1,
		    d[0][a - 1]
		    + ((chaine1[i - 1] == chaine1[a - 1]) ? 0
		       : 1));
    }
  }
  return d[1][tailleChaine2];
}

int min(int a, int b, int c) {
	if(a<=b && a<=c){
		return a;
	}
	else if(b<=a && b<=c){
		return b;
	}
	else{
		return c;
	}
}

int main(){
  char* chaine1 = "tatoa";
    char* chaine2 = "tbtob";
    printf("Distance = %d\n",distanceEdition(chaine1, chaine2, 5, 5));
  return 0;
}
